/*
 * mm-naive.c - The fastest, least memory-efficient malloc package.
 * 
 * In this naive approach, a block is allocated by simply incrementing
 * the brk pointer.  A block is pure payload. There are no headers or
 * footers.  Blocks are never coalesced or reused. Realloc is
 * implemented directly using mm_malloc and mm_free.
 *
 * NOTE TO STUDENTS: Replace this header comment with your own header
 * comment that gives a high level description of your solution.
 */
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <unistd.h>
#include <string.h>
#include "mm.h"
#include "memlib.h"

/*********************************************************
 * NOTE TO STUDENTS: Before you do anything else, please
 * provide your team information in the following struct.
 ********************************************************/
team_t team = {
    .teamname = "group-8",                /* Team name */

    .name1    = "孙  宇",                   /* First member full name */
    .id1      = "1226598193@qq.com",      /* First member email address */

    .name2     = "颜  申",                   /* Second member full name (leave blank if none) */
    .id2      = "1256208355@qq.com",      /* Second member email addr (leave blank if none) */

	.name3     = "孙添琦",                  /* Third member full name (leave blank if none) */
	.id3      = "406796052@qq.com"        /* Third member full name (leave blank if none) */
};

/* single word (4) or double word (8) alignment */
#define ALIGNMENT 8
/* rounds up to the nearest multiple of ALIGNMENT */
#define ALIGN(size) (((size) + (ALIGNMENT-1)) & ~0x7)

#define SIZE_T_SIZE (ALIGN(sizeof(size_t)))

#define WORDSIZE 	4      				// 字大小
#define DWORDSIZE 	8					// 双字大小
#define CHUNKSIZE 	(1<<12)				// linux的页大小

#define MAX(x,y) 			((x)>(y)?(x):(y))			

#define PACK(size,alloc) 	((size)|(alloc))	

#define GET(p)				(*(unsigned int *)(p))			
#define PUT(p,val)			(*(unsigned int *)(p)=(val))	

#define GET_SIZE(p)			(GET(p)&~0x7)			
#define GET_ALLOC(p)		(GET(p)&0x1)

#define HDRP(bp) 			((char *)(bp)-WORDSIZE)
#define FTRP(bp) 			((char *)(bp)+GET_SIZE(HDRP(bp))-DWORDSIZE)

#define NEXT_BLKP(bp) 		((char *)(bp)+GET_SIZE(((char *)(bp))-WORDSIZE))
#define PREV_BLKP(bp) 		((char *)(bp)-GET_SIZE(((char *)(bp))-DWORDSIZE))

static char *heap_listp;

/*找出最佳适配asize的块,若没有则返回NULL*/
static void *find_fit(size_t asize){
	void *bp;
	void *opt_fit = NULL;
	size_t offset = 0x7fffffff;
	for (bp = heap_listp; GET_SIZE(HDRP(bp)) > 0; bp = NEXT_BLKP(bp)){
		if(!GET_ALLOC(HDRP(bp)) && (asize <= GET_SIZE(HDRP(bp)))){
			if(GET_SIZE(HDRP(bp)) - asize < offset){
				opt_fit = bp;
				offset = GET_SIZE(HDRP(bp)) - asize;
			}
		}
	}
	return opt_fit;
}

/*把待分配块bp的大小设置为asize,在这个过程中决定大分配块是否要分割成更小的块*/
static void place(void *bp,size_t asize){
	size_t csize = GET_SIZE(HDRP(bp));
	if( (csize-asize) >= (2*DWORDSIZE) ){	// 若当前块中填充区域的大小大于2个双字大小,则把当前块进行分块
		PUT(HDRP(bp),PACK(asize,1));
		PUT(FTRP(bp),PACK(asize,1));
		bp = NEXT_BLKP(bp);
		PUT(HDRP(bp),PACK(csize-asize,0));
		PUT(FTRP(bp),PACK(csize-asize,0));
	}
	else{
		PUT(HDRP(bp),PACK(csize,1));
		PUT(FTRP(bp),PACK(csize,1));
	}
}

/*对块bp进行回收时,进行相邻块的合并操作,返回合并后的块指针*/
static void *coalesce(void *bp){
	size_t prev_alloc 	= GET_ALLOC(FTRP(PREV_BLKP(bp)));
	size_t next_alloc 	= GET_ALLOC(HDRP(NEXT_BLKP(bp)));
	size_t size 		= GET_SIZE(HDRP(bp));

	if(prev_alloc && next_alloc){                	// 上下都不能合并
		return bp;
	}	
	else if(prev_alloc && !next_alloc){				// 下面(next)能合并
		size += GET_SIZE(HDRP(NEXT_BLKP(bp)));		
		PUT(HDRP(bp),PACK(size,0));
		PUT(FTRP(bp),PACK(size,0));
	}
	else if(!prev_alloc&& next_alloc){				// 上面(prev)能合并
		size += GET_SIZE(HDRP(PREV_BLKP(bp)));
		PUT(FTRP(bp),PACK(size,0));
		PUT(HDRP(PREV_BLKP(bp)),PACK(size,0));
		bp = PREV_BLKP(bp);
	}
	else{											// 上下都能合并
		size += GET_SIZE(HDRP(PREV_BLKP(bp))) + GET_SIZE(FTRP(NEXT_BLKP(bp)));
		PUT(HDRP(PREV_BLKP(bp)),PACK(size,0));	
		PUT(FTRP(NEXT_BLKP(bp)),PACK(size,0));		
		bp = PREV_BLKP(bp);
	}
	return bp;
}
/*扩张堆区的大小,扩张的单位为字*/
static void *extend_heap(size_t words){
	char *bp;
	size_t size;
	size = (words%2) ? (words+1)*WORDSIZE : words*WORDSIZE;		// 边界调整
	if( (long)(bp = mem_sbrk(size)) == -1)
		return NULL;
	PUT(HDRP(bp),PACK(size,0));
	PUT(FTRP(bp),PACK(size,0));
	PUT(HDRP(NEXT_BLKP(bp)),PACK(0,1));							// 置尾部 0|1
	return coalesce(bp);										// 尝试向上合并
}

/*把source处的size个字节的数据copy到dest处*/
void sy_copy(void *dest, void *source, size_t size){
	if(!source && !dest){
		for(int i = 0; i < size;i++){
			((char *)dest)[i] = ((char *)source)[i];
		}
	}
}

/* 
 * mm_init - initialize the malloc package.
 */
int mm_init(void)
{
    if( ( heap_listp = mem_sbrk(4*WORDSIZE) ) == (void *)-1 )
    	return -1;
   	PUT(heap_listp,0);
   	PUT(heap_listp+(1*WORDSIZE),PACK(DWORDSIZE,1));
   	PUT(heap_listp+(2*WORDSIZE),PACK(DWORDSIZE,1));
   	PUT(heap_listp+(3*WORDSIZE),PACK(0,1));
   	heap_listp+=(2*WORDSIZE);
   	if(extend_heap(CHUNKSIZE/WORDSIZE) == NULL)
   		return -1;
    return 0;
}

/* 
 * mm_malloc - Allocate a block by incrementing the brk pointer.
 *     Always allocate a block whose size is a multiple of the alignment.
 */
void *mm_malloc(size_t size)
{
    	size_t 	asize;
		size_t 	extern_dword;
		char	*bp;

		if(size == 0)
			return NULL;		
		asize = ALIGN(size) + DWORDSIZE;		// align adjust

		if((bp = find_fit(asize)) != NULL){
			place(bp,asize);
			return bp;
		}
		extern_dword = MAX(asize, CHUNKSIZE);
		if((bp = extend_heap(extern_dword/WORDSIZE)) == NULL)
			return NULL;
		place(bp, asize);
		return bp;
}

/*
 * mm_free - Freeing a block does nothing.
 */
void mm_free(void *bp)
{
	size_t size = GET_SIZE(HDRP(bp));
	PUT(HDRP(bp),PACK(size,0));
	PUT(FTRP(bp),PACK(size,0));
	coalesce(bp);
}

/*
 * mm_realloc - Implemented simply in terms of mm_malloc and mm_free
 */

void *mm_realloc(void *ptr, size_t size)
{
    void *oldptr = ptr;
    void *newptr;
    size_t copySize;    
    newptr = mm_malloc(size);			// 申请size大小的空间,若size=0则newptr=NULL

	if(oldptr == NULL){					
		return newptr;
	}
	
    if (oldptr != NULL && size == 0){
		mm_free(oldptr);
		return NULL;
	}

	copySize = GET_SIZE(HDRP(oldptr)) - DWORDSIZE;
    sy_copy(newptr, oldptr, copySize);
    mm_free(oldptr);
    return newptr;
}